import collections
import heapq
class Solution(object):
    def findMaximizedCapital(self, k, w, profits, capital):
        """
        :type k: int
        :type w: int
        :type profits: List[int]
        :type capital: List[int]
        :rtype: int
        """
        c = list(set(capital))
        c.sort()
        d = collections.defaultdict(set)
        n = len(capital)
        for i in range(n):
            d[capital[i]].add(i)
        index = 0
        m = len(c)
        stack = []
        while index < m and c[index] <= w:
            for item in d[c[index]]:
                heapq.heappush(stack, - profits[item])
            index += 1
        while stack and k > 0:
            w -= heapq.heappop(stack)
            k -= 1
            while index < m and c[index] <= w:
                for item in d[c[index]]:
                    heapq.heappush(stack, - profits[item])
                index += 1
        return w



